package jjn.round1;

import java.util.*;

/**
 * @author Jiang Jining
 * @since 2023-06-22 12:50
 */
public class Interview_16_19_bfs {
    public int[] pondSizes(int[][] land) {
        int height = land.length;
        int width = land[0].length;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (land[i][j] == 0) {
                    result.add(bfs(land, i, j));
                }
            }
        }
        int[] sorted = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            sorted[i] = result.get(i);
        }
        Arrays.sort(sorted);
        return sorted;
    }
    
    private int bfs(int[][] land, int i, int j) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{i, j});
        land[i][j] = -1;
        int count = 0;
        while (!queue.isEmpty()) {
            int[] polled = queue.poll();
            int curY = polled[0], curX = polled[1];
            count++;
            for (int k = -1; k <= 1; k++) {
                for (int l = -1; l <= 1; l++) {
                    if (k == 0 && l == 0) {
                        continue;
                    }
                    if (curY + k < 0 || curY + k >= land.length) {
                        continue;
                    }
                    if (curX + l < 0 || curX + l >= land[0].length) {
                        continue;
                    }
                    if (land[curY + k][curX + l] != 0) {
                        continue;
                    }
                    land[curY + k][curX + l] = -1;
                    queue.offer(new int[]{curY + k, curX + l});
                }
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        int[][] land = new int[][]{{0, 2, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 0, 1}};
        int[] result = new Interview_16_19_bfs().pondSizes(land);
        System.out.println("Arrays.toString(result) = " + Arrays.toString(result));
    }
}
